package BinaryTree;

//二叉树的最近公共祖先: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
//时间复杂度: O(n)
public class LowestCommonAncestor {
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		//先判断节点是否 遇到空，或者遇到p,或者遇到q，返回
        if(root==null||root==p||root==q){
            return root;
        }
        //递归左子树,看是否会遇到p或者q
        TreeNode l=lowestCommonAncestor(root.left,p,q);
        //递归右子树,看是否会遇到p或者q
        TreeNode r=lowestCommonAncestor(root.right,p,q);
        //如果左子树和右子树包含p,q，显然最近公共祖先为root
        if(l!=null&&r!=null){
            return root;
        }
        //如果左子树和右子树不包含p,q，显然root不是公共祖先，返回null,
        //表示以当前root为根的树，不存在p,q的公共祖先
        if(l==null&&r==null){
            return null;
        }
        //如果一侧找到了p/q，则直接返回找到的节点
        //如果p,q在同侧，p包含q，则只要遇到p就可以直接返回，该语句包含了p包含q的情况
        return l!=null?l:r;
    }
}
